Most modern computers use a virtual addressing scheme which allows the computer to address an address space that is larger than the computer's internal memory. In such a scheme, a virtual address must be translated to a physical address before the memory can be accessed. Unfortunately, each translation process ordinarily requires multiple accesses to page and segment tables in the computer's memory, which significantly degrades the computer's performance.
To overcome this problem, a translation lookaside buffer (TLB) is often used to maintain the most recently used virtual address and physical address mappings. Each TLB entry ordinarily contains a virtual address, a real address mapped to the virtual address, and sometimes, control information such as access protection flags, etc. Before translating an input virtual address in the conventional manner, the TLB is searched to see if a physical address mapping for the virtual address is present. If a physical address mapping is present in the TLB, the physical address may be obtained directly from the TLB, and the conventional time-wasting translation process is avoided.
FIG. 1 is a block diagram of a known TLB 100 which stores a set of virtual address/physical address translations. TLB 100 comprises a content addressable memory (CAM) array 104 for storing a plurality of virtual addresses, a static random-access memory (SRAM) array 108 for storing a plurality of physical addresses corresponding to the virtual addresses stored in CAM array 104, a CAM word line decoder 112 for receiving a line address from the CPU over a communication path 116, a CAM bit line driver 120 for receiving a virtual address from the CPU over a communication path 122, an SRAM bit line driver 124 for receiving a physical address from the CPU over a communication path 126, an array interface 130 for accessing SRAM array 108 in response to signals from CAM array 104 and from CAM word line decoder 112, and an SRAM bit line sense amplifier 134 for providing a physical address stored in SRAM array 108 to the CPU over a communication path 136.
CAM array 104 comprises a plurality of CAM cells 140(0,0) . . . 140(N,X) arranged in N rows and X columns. Each row of CAM cells 140(0,0-X) . . . 140(N,0-X) stores a single X-bit virtual address and is coupled to one of a plurality of CAM word lines 144(0) . . . 144(N) from CAM word line decoder 112. Each column of CAM cells 140(0-N,0) . . . 140(0-N,X) is coupled to a corresponding pair of a plurality of differential CAM bit lines 146(0) . . . 146(X), 148(0) . . . 148(X) from CAM bit line driver 120. CAM word lines 144(0) . . . 144(N) and CAM bit lines 146(0) . . . 146(X), 148(0) . . . 148(X) activate the CAM cells 140(0,0) . . . 140(N,X) to which they are attached. Each row of CAM cells 140(0,0-X) . . . 140(N,0-X) is also connected to one of a plurality of match lines 152(0) . . . 152(N) for indicating which row of CAM cells 140(0,0-X) . . . 140(N,0-X) stores the virtual address which matches the virtual address input to CAM bit line driver 120
Similarly, SRAM array 108 comprises a plurality of SRAM cells 156(0,0) . . . 156(N,Y) arranged in N rows and Y columns. Each row of SRAM cells 156(0,0-Y) . . . 156(N,0-Y) stores a single Y-bit physical address and is coupled to one of a plurality of SRAM word lines 160(0) . . . 160(N) from array interface 130. Each column of SRAM cells 156(0-N,0) . . . 156(0-N,Y) is coupled to a corresponding pair of a plurality of differential SRAM bit lines 162(0) . . . 162(Y), 164(0) . . . 164(Y) from SRAM bit line driver 124. SRAM word lines 160(0) . . . 160(N) and SRAM bit lines 162(0) . . . 162(Y), 164(0) . . . 164(Y) activate the SRAM cells 156(0,0) . . . 156(N, Y) to which they are attached. SRAM bit lines 162(0) . . . 162(Y), 164(0) . . . 164(Y) are also coupled to SRAM bit line sense amplifier 134 for providing the contents of the selected row of SRAM cells to the CPU.
Array interface 130 comprises a plurality of OR gates 168(0) . . . 168(N). Each OR gate 168(0) . . . 168(N) has a first input terminal coupled to a corresponding one of CAM word lines 144(0) . . . 144(N), a second input terminal coupled to a corresponding one of match lines 152(0) . . . 152(N) through corresponding sense amplifiers 172(0) . . . 172(N), and an output terminal coupled to a corresponding one of SRAM word lines 160(0) . . . 160(N). Array interface 130 selects one of the rows of SRAM cells 156(0,0-Y) . . . 156(N,0-Y) in response to CAM word lines 144(0) . . . 144(N) during a non-associative mode of operation (discussed below), and array interface 130 selects one of the rows of SRAM cells 156(0,0-Y) . . . 156(N,0-Y) in response to match lines 152(0) . . . 152(N) during an associative mode of operation.
The non-associative mode of operation includes either a write access or a read access. During a non-associative write access, a virtual address from the CPU is provided to CAM bit line driver 120 over communication path 122, a physical address from the CPU is provided to SRAM bit line driver 124 over communication path 126, and a write address is supplied from the CPU to CAM word line decoder 112 over communication path 116. CAM word line decoder 112 decodes the address received over communication path 116 and generates a high signal on a single CAM word line 144(I) from the plurality of CAM word lines 144(0) . . . 144(N) for activating CAM cells 140(I,0-X). The high signal on CAM word line 144(I) also causes the corresponding OR gate 168(I) in array interface 130 to generate a high signal on SRAM word line 160(I) for activating SRAM cells 156(I,O-Y). The virtual and physical addresses then may be written into CAM array 104 and SRAM array 108 at locations defined by the activated CAM cells 140(I,0-X) and SRAM cells 156(I,0-Y), respectively.
A non-associative read access operates the same way, except addresses are not supplied to CAM bit line driver 120 or SRAM bit line driver 124. The addressed physical address is output from SRAM bit line sense amp 134 over communication path 136.
During the associative mode of operation, a virtual address is input to CAM bit line driver 120, and the input virtual address is simultaneously compared with all virtual addresses stored in CAM array 104. If the input virtual addresses matches a virtual address stored in CAM array 104 (e.g., in CAM cells 140(I,0-X)), then a high signal is generated on the appropriate match line (e.g., match line 152(I)). The high signal is detected by sense amp 172(I), which in turn causes a high signal to be generated by OR gate 168(I). The high signal from OR gate 168(I) activates SRAM cells 156(I,0-Y) for communicating the stored physical address to SRAM bit line sense amp 134 and thereafter to the CPU over communication path 136.
A TLB implemented in this manner has the primary drawback of requiring extra time to output a physical address from SRAM array 108 during an associative access because array interface 130 includes OR gates 168(0) . . . 168(N) having match lines 152(0) . . . 152(N) and CAM word lines 144(0) . . . 144(N) as inputs. During an associative access, signals on match lines 152(0) . . . 152(N) which indicate if a match has been found on a match line 152(I) must propagate through OR gates 168(0) . . . 168(N) before the physical address stored in SRAM array 108 is output to the CPU.
The time it takes for TLB 100 to output a physical address once a matching virtual address has been found is of critical importance. The path a signal on match line 152(I) travels from the point a match is found until the physical address is output from SRAM 108 is commonly referred to as the "critical path." OR gates 168(0) . . . 168(N) are situated in the critical path so that they add an undesirable delay to associative accesses and reduce the performance of TLB 100.
FIG. 2 is a block diagram of a known TLB 200 which attempts to overcome the primary disadvantage of TLB 100 in that there is no additional delay in outputting a physical address from TLB 200 during the associative access mode. The TLB illustrated in FIG. 2 is discussed in "A 4-ns BiCMOS Translation-Lookaside Buffer" in IEEE Journal of Solid-State Circuits, Vol. 25, No. 5. For convenience of describing the operation of TLB 200, the same reference numerals used in FIG. 1 are used in FIG. 2 to refer to identical elements. Furthermore, the operation of TLB 200 is identical to the operation of TLB 100 except in the manner in which SRAM array 108 is accessed during both associative and non-associative modes.
TLB 200 comprises the same components as TLB 100 except that an array interface 205 replaces array interface 130. Additionally, TLB 200 comprises an SRAM word line decoder 210 for receiving a line address from the CPU over a communication path 215 and for accessing the rows of SRAM cells with output lines 220(0) . . . 220(N) which are coupled to rows of SRAM cells 156(0,0-Y) . . . 156(N,0-Y).
Array interface 205 comprises a plurality of sense amplifiers 172(0) . . . 172(N). Each sense amplifier 172(0) . . . 172(N) has an input terminal coupled to a corresponding one of match lines 152(0) . . . 152(N) and an output terminal coupled to a corresponding one of SRAM word lines 160(0) . . . 160(N). Array interface 205 selects one of the rows of SRAM cells 156(0,0-Y) . . . 156(N,0-Y) in response to match lines 152(0) . . . 152(N) during the associative mode.
During a non-associative write access, a virtual address from the CPU is provided to CAM bit line driver 120 over communication path 122, a physical address from the CPU is provided to SRAM bit line driver 124 over communication path 126, and a write address is supplied from the CPU to CAM word line decoder 112 over communication path 116 and to SRAM word line decoder 210 over communication path 215. CAM word line decoder 112 decodes the write address received over communication path 116 and generates a high signal on a single CAM word line 144(I) from the plurality of CAM word lines 144(0) . . . 144(N) for activating CAM cells 140(I,O-X). SRAM word line decoder 210 decodes the write address received over communication path 215 and generates a high signal on a output line 220(I) from the plurality of output lines 220(0) . . . 220(N). Output line 220(I) then activates SRAM cells 156(I,O-Y). The virtual and physical addresses then may be written into CAM array 104 and SRAM array 108 at locations defined by the activated CAM cells 140(I,0-X) and SRAM cells 156(I,0-Y), respectively.
A non-associative read access operates the same way, except addresses are not supplied to CAM bit line driver 120 or SRAM bit line driver 124, a write address is not supplied to CAM word line decoder 112, and the addressed physical address is output from SRAM bit line sense amp 134 over communication path 136.
During an associative access, a virtual address is input to CAM bit line driver 120, and the input virtual address is simultaneously compared with all virtual addresses stored in CAM array 104. If the input virtual address matches a virtual address stored in CAM array 104 (e.g., in CAM cells 140(I,0-X)), then a high signal is generated on the appropriate match line (e.g., match line 152(I)). The high signal is detected by sense amp 172(I) which activates SRAM cells 156(I,0-Y) for communicating the stored physical address to SRAM bit line sense amp 134 and thereafter to the CPU over communication path 136.
Prior art devices using the technique employed by TLB 200 have two major drawbacks. First, SRAM array 108 must be dual port memory arrays which is more expensive than comparable single port memories. Second, a TLB implemented in this manner requires the use of two word line decoders which results in increased hardware costs and less available chip area.